Search for: All records

A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $$T$$ with $$n$$~edges, it is conjectured that there exists a labeling $$f\colon V(T) \to \{0,1,\ldots,n\}$$ such that the set of induced edge labels $$\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$$ is exactly $$\{1,2,\ldots,n\}$$. We extend this concept to allow for multigraphs with edge multiplicity at most~$$2$$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $$G$$ with $$n$$~edges is a one-to-one function $$f\colon V(G) \to \{0,1,\ldots,n\}$$ such that the multiset of induced edge labels is comprised of two copies of each element in $$\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$$ and, if $$n$$ is odd, one copy of $$\bigl\{ \lceil n/2 \rceil \bigr\}$$. When $$n$$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $$n \not\equiv 1 \pmod{4}$$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $$2$$-fold graceful. 

Let $$G$$ be one of the two multigraphs obtained from $$K_4-e$$ by replacing two edges with a double-edge while maintaining a minimum degree of~2. We find necessary and sufficient conditions on $$n$$ and $$\lambda$$ for the existence of a $$G$$-decomposition of $$^{\lambda}K_n$$. 

Consider the multigraph obtained by adding a double edge to $$K_4-e$$. Now, let $$D$$ be a directed graph obtained by orientating the edges of that multigraph. We establish necessary and sufficient conditions on $$n$$ for the existence of a $$(K^{*}_{n},D)$$-design for four such orientations.